The availability and use, of computers has become nearly ubiquitous in modern society. Computers, such as personal computers (PCs), are in wide use today in homes and businesses for information management tasks such as word processing, accounting, graphics, imaging, data management, communications, etc. Many computer based information management systems store, associate, present, and/or represent various elements (e.g., data files, file system folders, electronic communications, etc.) using a hierarchical data structure. Such hierarchical structures allow for logical grouping of the information, such as into several levels of files or folders. This hierarchical organization generally facilitates a user's easy access to specific desired data within a much larger data repository.
FIG. 1 is a diagram illustrating hierarchical data structure 110 as provided within repository 100. Such hierarchical data structures are often described as trees having various branches and leaf nodes. Because of the hierarchical nature, descriptors, such as parent, sibling, and children are used to describe the hierarchical relationship between the various files, folders, and nodes in the structure. Hierarchical data structure 110 includes two main branches represented by elements A and D, such as may comprise folders, files, etc. Elements A and D are in the top most hierarchy of hierarchical structure 110 (i.e., directly below the hierarchy root), they are siblings to each other. In association with these two top level elements are element B, which is a child of element A and element E, which is a child of element D. For example, element A and element D may comprise folders within which are element B and element E which are themselves folders, but still do not represent any actual data. The data in hierarchical data structure 110 is represented by element C and element M, which are children of element B, and element F, which is a child of element E. Continuing with the foregoing example, elements C, M, and F may comprise files within a respective one of elements B and E. Hierarchical data structure 110 may be organized such that particular elements, such as elements C and M, represent information of a much different nature than that of other elements, such as element F. Therefore, when reviewing hierarchical data structure 110 of the entire data repository, a user may easily bypass the entire branch of element D and proceed directly to the branch of element A to find the desired file.
Information for such repositories may be gathered and stored in various different manners and with various different devices, such as digital cameras, digital music players, a variety of computer applications, such as word processors, spread sheets, mobile phones, and the like. There may also be multiple repositories or instances of the same information. For example, music on a digital music player may exist on the player device and also on the user's computer. Photographs from a digital camera may exist on one or more of a user's computer and also in an online photo service. In networked environments, it may be beneficial to have a set of information stored on a networked or shared memory and also on a local memory, such that a user may be able to access the information either while logged onto the network or operating offline and possibly remote from the networked environment.
One of the functionalities or utilities that relates to the foregoing multiple data instances is synchronization. Synchronization is the process of making the data on one of the devices or networked locations equal to or synchronized with the data on the other device or network location. That is, synchronization is the act of keeping the state of a repository of elements consistent between two targets. Such targets are referred to herein as sync targets, wherein a sync target is an application that maintains a repository of elements facilitating a user add/delete/edit elements to/in the repository (e.g., PHOTOSHOP.COM™ online image editing application, PHOTOSHOP® ELEMENTS image editing software, etc.). Such sync targets may contain hierarchical data, such as within a hierarchical data structure as shown in FIG. 1, thereby providing hierarchical targets containing hierarchical data which needs to be synchronized.
An example of hierarchical targets is a list of albums in PHOTOSHOP.COM™ and PHOTOSHOP® ELEMENTS. Such an album hierarchy data structure can contain an album inside an album group wherein each element in the hierarchy can be independently edited/moved/deleted. If, for example, new data has been added to one of the hierarchical targets (e.g., added to a file in one of hierarchical targets), it should be correspondingly added to associated hierarchical targets (e.g., added to a corresponding file or files in the other hierarchical targets) as well if synchronization is to be maintained. Accordingly, it should be appreciated that synchronization of hierarchical targets involves synchronizing attributes of each element in the hierarchy as well as synchronizing relationships present in the hierarchy.
Providing synchronization with respect to hierarchical targets presents challenges both with respect to efficient operation and accurately maintaining synchronization. For example, implementing a “brute force” approach might propagate/commit changes across the hierarchical targets as each change is made. However, such an approach results in a lack of efficiency because multiple passes through the hierarchical data structures would be made for a series of changes (e.g., the hierarchy of elements would be computed multiple times to synchronize a plurality of changes). However, certain use cases present challenges when attempting to propagate/commit a plurality of changes in batch. For example, deletion of a parent element in a hierarchy (deletion of a parent implies deletion of all of its children) can present synchronization issues where the children elements of the deleted parent element were moved prior to the deletion.